#include "GreedyFillMaximalGroupAlgorithm.h"
#include "Helpers.h"
#include "GreedyFillGroupAlgorithm.h"
#include <math.h>

using std::set;
using std::vector;

/*****************************************************************************/
// GreedyFillMaximalGroupAlgorithm
// Algorithm for filling an independent group (while keeping it independent), 
// using greedy algorithms for single vertices and for couples.
// 1. Fill the initial group using greedy fill algorithm for singles 
// (GreedyFillGroupAlgorithm::FillSingles).
// 2. Iterations trying to replace the initial group with better ones:
//    2.1 run greedy fill algorithm for singles on an empty group, until a 
//        certain bar is reached.
//    2.1 run greedy fill algorithm for couples on the group from 2.1, until a 
//        certain bar is reached.
//    2.1 run greedy fill algorithm for singles on the group from 2.2, until it 
//        is maximal.
// 3. Return the best (biggest) group found over all the iterations.
//
// Input: Graph G=(V,E); independent Group S to be filled; 
// integer iterations: number of iterations to run before returning the best option;
// double startCouplesPercent: percent of vertices in S for switching from 2.1 to 2.2
// double:stopCouplesPercent: percent of vertices in S for switching from 2.1 to 2.2
// int couplesNum: number of couples to check before choosing a couple with the lowest
// rank.
// Output: The graph G & the group S after filling S.
//
/*****************************************************************************/

//---------------------------------------------------------------------------------------------------
// Fill method: The method that does the actual filling of a group, for 
// a single vertex.
// Parameters: 
// graph - the graph data structure. Notice that this parameter is 
// also an output parameter as the graph changes when we fill a group.
// group - the group to be filled. May be empty.
// improveGroup: If true, the algorithm will first try to improve the given group, 
// before trying to replace it with a new group		
// Output:
// The new group after filling. The gaph is also changed.
// A note about implementation:
// In this algorithm we use 2 copies of our "world" (group, graph, vertex directory) simultaneously.
// We use one copy to backup the given 3 instances.
// In each itertaion we create new copies and run all operations on them.
// If the iteration is deemed successful, we copy it into the backup copies.
// Only in the end of the algorithm we copy the most successful result into the given instances.
// Note: This method may throw an std::bad_alloc exception due to memory allocation memory
// when initiating a copy of the vertex directory.
//--------------------------------------------------------------------------------------------------
Group& GreedyFillMaximalGroupAlgorithm::Fill(Graph& graph  /* also output parameter */, Group& group, 
											 int iterations, double startCouplesPercent, 
											 double stopCouplesPercent, int couplesNum, 
											 VertexDirectory* directory, bool improveGroup)
{
	Logger::LogMessage("Running fill singles-couples-singles on group "+group.PrintName());
	// create a VertexDirectory copy and use it in this run (so we don't influance the state of the graph)
	VertexDirectory* dir;
	if (directory == NULL)
	{	// use static vertex directory to create the copy
		dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
	}
	else
	{	// use the procided vertex directory to create the copy
		dir = new VertexDirectory(directory->GetWorkingCopyVertices());
	}
	
	// all operations are done on a copy of the graph, since we remove neighbours that should appear
	// in the graph when the algorithm finishes running
	Graph* tempGraph = graph.CloneFromDirectory(dir);
	if (tempGraph == NULL)	//memory allocation failed
	{
		delete dir;
		Logger::LogMessage("ERROR: Unable to create graph in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create graph in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
	}

	// all operations are done on a copy of the group	
	Group* tempGroup;
	try
	{
		tempGroup = new Group(group, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		delete tempGraph;
		delete dir;
		Logger::LogMessage("ERROR: Unable to create group in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
		throw new GraphColoringException("ERROR: Unable to create group in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
	}

	// Fill the group with no limitation on the group size, only if the group should be 
	// improved before trying to replace it with a new & improved group
	if (improveGroup == true)
	{
		*tempGroup = GreedyFillGroupAlgorithm::FillSingles(*tempGraph, *tempGroup, dir,Algorithms::_NO_SIZE_LIMITATION);
	}
	//calculate criteria for starting and stoping couples greedy algorithm
	int groupSize = tempGroup->Size();
	int startCouplesFill = (int)(floor(groupSize * startCouplesPercent) / 100);
	int stopCouplesFill = (int)(floor(groupSize * stopCouplesPercent) / 100);
	
	for (int i=0; i < iterations; i++)
	{
		// create copies to run this iteration on, the copies will use the copied vertex directory
		// this is because we want to get updated info on the vertices AFTER we filled the original group
		// using the greedy FillSingles algorithm
		VertexDirectory* iterationDir;
		try
		{
			iterationDir = new VertexDirectory(dir->GetWorkingCopyVertices());
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e = NULL;
			delete tempGroup;
			delete tempGraph;
			delete dir;
			Logger::LogMessage("ERROR: Unable to create vertex directory in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
			throw new GraphColoringException("ERROR: Unable to create vertex directory in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
		}

		Graph* tempIterationGraph = tempGraph->CloneFromDirectory(iterationDir);
		if (tempIterationGraph == NULL)	//memory allocation failed
		{
			delete iterationDir;
			delete tempGroup;
			delete tempGraph;
			delete dir;
			Logger::LogMessage("ERROR: Unable to create graph in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
			throw new GraphColoringException("ERROR: Unable to create graph in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
		}
		//spill the tempGroup back into the graph and try to create a better one
		tempIterationGraph->AddGroup(*tempGroup);

		// create a new group and try to fill it
		Group* tempIterationGroup;
		try
		{
			tempIterationGroup = new Group(Algorithms::_TEMP_GROUP_NAME, iterationDir);
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e = NULL;
			delete tempIterationGraph;
			delete iterationDir;
			delete tempGroup;
			delete tempGraph;
			delete dir;
			Logger::LogMessage("ERROR: Unable to create group in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
			throw new GraphColoringException("ERROR: Unable to create group in GreedyFillMaximalGroupAlgorithm. Algorithm didn't run.");
		}
		*tempIterationGroup = GreedyFillGroupAlgorithm::FillSingles(*tempIterationGraph, *tempIterationGroup, iterationDir, startCouplesFill);
		*tempIterationGroup = GreedyFillGroupAlgorithm::FillCouples(*tempIterationGraph, *tempIterationGroup, iterationDir, stopCouplesFill);
		*tempIterationGroup = GreedyFillGroupAlgorithm::FillSingles(*tempIterationGraph, *tempIterationGroup, iterationDir, Algorithms::_NO_SIZE_LIMITATION);

		if (tempIterationGroup->Size() > groupSize)
		{ // tempIterationGroup is bigger - keep it: copy all data from the iteration copies
			// update the graph & the group
			tempGraph->AddGroup(*tempGroup);
			Algorithms::UpdateGraphAndGroupFromCopies(*tempGraph, *tempGroup, *tempIterationGroup);
			// update the group size to the new size..
			groupSize = tempGroup->Size();
		}
		delete tempIterationGraph;
		delete tempIterationGroup;
		delete iterationDir;
	}
	// all updates finished - update the given group & graph instances to the best result
	// if we've improved the group - update the graph and the group to the improved result
	if (tempGroup->Size() > group.Size())
	{
		graph.AddGroup(group);
		Algorithms::UpdateGraphAndGroupFromCopies(graph, group, *tempGroup);
	}
	delete tempGraph;
	delete tempGroup;
	delete dir;
	return group;
}




